#include "DynamicArray.h"
#include "DynamicArray.h"
#include<stdlib.h>
#include<stdio.h>



typedef struct DynamicArray
{
    ElementType *array;//数组指针
    int capacity;//数组容量
    int size;//数组大小
    void (*FreePtr)(ElementType);//释放函数的函数指针
} DArray;

DArray *InitDArray(int capacity,void(*FreePtr)(ElementType))
{
    DArray *a = (DArray*)malloc(sizeof(DArray));
    if(a==NULL)
    {
        printf("申请空间失败");
        return NULL;
    }
    a->FreePtr = FreePtr;
    a->capacity = capacity;
    a->size = 0;
    a->array = (ElementType*)malloc(sizeof(ElementType) * a->capacity);
        if(a->array==NULL)
    {
        free(a);
        printf("申请数组失败");
        return NULL;
    }
    return a;
}

void FreeDArray(void *ptr)
{
    DArray *a = (DArray *)ptr;
    if (a)
    {
        if (a->FreePtr != NULL)
        {
            for (int i = 0; i < a->size; i++)
            {
                a->FreePtr(a->array[i]);
            }
        }
        if (a->array != NULL)
        {
            free(a->array);
        }
        free(a);
}
}

bool InsertTail(DArray *a, ElementType element)
{
    if(a->size >= a->capacity)
    {
        ElementType *oldP = a->array;
        a->array = (ElementType*)malloc(a->capacity * 2 * sizeof(ElementType));
        if(a->array == NULL)
        {
            printf("扩容失败\n");
            return false;
        }
        a->capacity *= 2;
        for (int i = 0; i < a->size; i++)
        {
            a->array[i] = oldP[i];
        }
        free(oldP);
    }
    a->array[a->size] = element;
    a->size++;

    return true;
}

void PrintArray(DArray *a,void (*print)(ElementType))
{
    for (int i = 0; i < a->size; i++)
    {
        print(a->array[i]);
    }
    printf("\n");
}

void RemoveByIndex(DArray *a, int index)
{
    if(index<0||index>=a->size)
    {
        printf("非法删除位置！\n");
        return;
    }
    if(a->FreePtr!=NULL)
    {
        a->FreePtr(a->array[index]);
    }
    for (int i = index; i <a->size -1 ;i++)
    {
        
        a->array[i] = a->array[i + 1];
    }
    a->size--;
}

void RemoveByValue(DArray *a, ElementType element)
{
    for (int i = 0; i < a->size;i++)
    {
        if(a->array[i]==element)
        {
            RemoveByIndex(a, i);
            i--;
        }
    }
}

ElementType FindByElement(DArray *a, ElementType element, bool (*find)(ElementType, ElementType))
{
    for (int i = 0; i < a->size;i++)
    {
        if(find(a->array[i],element)==true)
            return a->array[i];
    }
    return NULL;
}



void FastSort(ElementType *a,int start, int end, bool (*SortPtr)(ElementType, ElementType))
{
     //终止条件
    if(start>=end)
        return;
    int left = start;
    int right = end;
    ElementType temp = a[left];
    while(left<right)
    {
        //先从右边动 找比基准值小的数
        while(SortPtr(a[right],temp)==true&&left<right)
        {
            right--;
        }
        //把右边的值赋给左边的空位
        if(left<right)
        a[left++] = a[right];
        //左边动，找比基准值大的数
        while(SortPtr(temp,a[left])==true&&left<right)
        {
            left++;
        }
        //把左边的值赋给右边的空位
        if(left<right)
            a[right--] = a[left];
    }
    a[left] = temp;
    //递归函数
    FastSort(a, start, left - 1,SortPtr);
    FastSort(a, right + 1, end,SortPtr);

}
void DArrayFastSort(DArray *a, bool (*SortPtr)(ElementType, ElementType))
{
    FastSort(a->array, 0, a->size-1, SortPtr);
}
//二分查找

ElementType BinarySearch(DArray *a, ElementType element, int (*BSearch)(ElementType, ElementType))
{
    int left = 0;
    int right = a->size - 1;
    while(left <= right)
    {
        int mid = left+(right-left)/2;
        //int mid = (left & right) + (left ^ right) >> 1;
        //比中间值小
        if(BSearch(a->array[mid],element)>0)
        {
            //左半边找
            right = mid - 1;
        }
        else if(BSearch(a->array[mid],element)<0)
        {
            //右半边找
            left = mid +1;
        }
        else
        {
            return a->array[mid];
        }
    }
    //没找到
    return NULL;
}
